package com.fantastic.array;

import javax.print.attribute.EnumSyntax;
import javax.sound.sampled.EnumControl;
import java.util.*;

/**
 * @author : fantastic
 * @date : 2024/5/20 16:39
 * @desc : this class for xxxxx
 **/
public class Solution {



    /*********************************************1. 两数之和**************************************************/
    /**
     * 1. 两数之和
     * 给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，
     * 并返回它们的数组下标。
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * 你可以按任意顺序返回答案。
     *
     * @return
     */
    public static int[] twoSum(int[] nums, int target) {
        int[] result = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    result[0] = i;
                    result[1] = j;
                    break;
                }
            }
        }
        return result;
    }

    /**
     * 哈希法
     *
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum1(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>(16);
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp)) {
                result[0] = map.get(temp);
                result[1] = i;
                break;
            } else {
                map.put(nums[i], i);
            }
        }
        return result;
    }



    /*************************************************4. 寻找两个正序数组的中位数**********************************************/
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //归并排序
        int[] result=new int[nums1.length+nums2.length];
        int i=0,j=0,k=0;
        while (i<nums1.length&&j< nums2.length){
            if (nums1[i]<=nums2[j]){
                result[k++]=nums1[i++];
            }else {
                result[k++]=nums2[j++];
            }
        }
        while (i<nums1.length){
            result[k++]=nums1[i++];
        }
        while (j<nums2.length){
            result[k++]=nums2[j++];
        }
        double res;
        if (result.length%2==0){
            int a=result.length/2;
            int b=a-1;
            res= (result[a]+result[b])/2.0;
        }else {
            res= result[result.length/2];
        }
        return res;
    }

    /*************************************************11. 盛最多水的容器**********************************************/
    /**
     * 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     * 说明：你不能倾斜容器。
     * 双指针，移动最小变，容量由最小的边决定
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        //解法暴力，提交直接超时
        int area=0;
        for (int i = 0; i < height.length-1; i++) {
            for (int j = i+1; j < height.length; j++) {
                int high = height[i] - height[j] >= 0 ? height[j] : height[i];
                int wide=j-i;
                area= Math.max((high * wide), area);
            }
        }
    return area;
    }

    public static int maxArea1(int[] height) {
        int left=0,right=height.length-1,area=0;
        while (left<right){
            //1、area=x*y,x=right - left,y=数组中两个位置最小的数决定容量，
            area = Math.max((right - left) * Math.min(height[left], height[right]), area);
            if (height[left]<=height[right]){
                ++left;
            }else {
                --right;
            }
        }
        return area;
    }


    /*************************************************15. 三数之和**********************************************/

    /**
     * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
     * 你返回所有和为 0 且不重复的三元组。
     * 注意：答案中不可以包含重复的三元组。
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        int i=0,j=i+1,k=j+1;
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<String> list=new ArrayList<>();
        while (i<nums.length-2){
            int sum = nums[i] + nums[j] + nums[k];
            if (sum==0){
                String s = nums[i] + "" + nums[j] + "" + nums[k];
                List<Integer> asList = Arrays.asList(nums[i], nums[j], nums[k]);
                if (!list.contains(s)){
                    list.add(s);
                    ans.add(asList);

                }

            }
            if (j<nums.length-2){
                ++j;
            }else if (k<nums.length-1){
                ++k;
            }else {
                ++i;
            }
        }
        return ans;
    }
        /*************************************************26. 删除有序数组中的重复项**********************************************/
    /**
     * 26. 删除有序数组中的重复项
     * 给你一个非严格递增排列的数组nums，请你原地删除重复出现的元素使每个元素只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
     * 然后返回 nums 中唯一元素的个数。
     * 考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
     * 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
     * 返回 k 。
     * [0,0,1,1,1,2,2,3,3,4]
     * [0,1,2,3,4]
     * 快慢指针
     *
     * @param nums
     * @return
     */
    public static int removeDuplicates(int[] nums) {
        int k = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[k++] = nums[i + 1];
            }
        }
        return k;
    }

    public static int removeDuplicates1(int[] nums) {
        if (nums.length == 0) {
            return nums.length;
        }
        int fast = 1, slow = 1;
        while (fast < nums.length) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }



    /*************************************************27. 移除元素**********************************************/


    /**
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
     * 假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
     * 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
     * 返回 k
     * 快慢指针
     *
     * @param nums
     * @param val
     * @return
     */
    public static int removeElement(int[] nums, int val) {
        if (nums.length == 0) {
            return nums.length;
        }
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }

    public static int removeElement1(int[] nums, int val) {
        if (nums.length == 0) {
            return nums.length;
        }
        //降低遍历次数，将左侧重复数据赋值到右侧
        int left = 0, right = nums.length;
        while (left < right) {
            if (nums[left] == val) {
                nums[left] = nums[right - 1];
                right--;
            } else {
                left++;
            }
        }
        return left;
    }

    /*************************************************35. 搜索插入位置**********************************************/
    /**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * 请必须使用时间复杂度为 O(log n) 的算法
     *
     * @param nums
     * @param target
     * @return
     */
    public static int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }


    /*************************************************55. 跳跃游戏**********************************************/

    /**
     * 给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。
     * @param nums
     * @return
     */
    public static boolean canJump(int[] nums) {
        if (nums.length == 1 || nums.length == 0) {
            return true;
        }
        boolean isJump = true;
        int i = 0;
        while (i < nums.length && isJump) {
            if (nums[i] == 0) {
                int j = i - 1;
                isJump = false;
                while (j >= 0) {
                    int temp = nums[j] - (i - j);
                    if (temp > 0 || (i == nums.length - 1 && temp == 0)) {
                        isJump = true;
                        break;
                    }
                    j--;
                }
            }
            i++;
        }
        return isJump;
    }


    public static boolean canJump2(int[] nums) {
        int rightMost=0;
        //贪心
        for (int i = 0; i < nums.length; i++) {
            if (i<=rightMost){
                rightMost = Math.max(rightMost, nums[i] + i);
                if (rightMost>=nums.length-1){
                    return true;
                }
            }
        }
        return false;
    }


    /*************************************************45. 跳跃游戏 II**********************************************/

    /**
     * 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
     * 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
     * 0 <= j <= nums[i]
     * i + j < n
     * 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
     * @param nums
     * @return
     */
    //TODO
    public static int jump(int[] nums) {





        return 0;
    }




    /*************************************************80. 删除有序数组中的重复项 II**********************************************/




    /**
     *给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     * @param nums
     * @return
     */
    public static int removeDuplicates_1(int[] nums) {
        int slow=2,fast=2;
        while (fast<nums.length){
            if (nums[slow-2]!=nums[fast]){
                 nums[slow]=nums[fast];
                 ++slow;
            }
            ++fast;
        }
        return slow;
    }


    /*************************************************66. 加一**********************************************/


    /**
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            //判断数据==9，则该位赋值为0，否则该位置+1直接返回，如果所有位置都为9，那么该数据向前进一位，首位置为1
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] = digits[i] + 1;
                return digits;
            }
        }
        int[] result = new int[digits.length + 1];
        result[0] = 1;
        return result;
    }

    /*************************************************88. 合并两个有序数组**********************************************/
    /**
     * 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
     * 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
     * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m+i]=nums2[i];
        }
        Arrays.sort(nums1);
    }
    public void merge2(int[] nums1, int m, int[] nums2, int n) {
        int[] sorted=new int[m+n];
        int p1=0,p2=0;
        int cur;
        while (p1<m||p2<n){
            if (p1==m){
                cur=nums2[p2++];
            }else if (p2==n){
                cur=nums1[p1++];
            }else if (nums1[p1]<=nums2[p2]){
                cur=nums1[p1++];
            }else {
                cur=nums2[p2++];
            }
            sorted[p1+p2-1]=cur;
        }
        for (int i = 0; i < sorted.length; i++) {
            nums1[i]=sorted[i];
        }
    }


    /*************************************************121. 买卖股票的最佳时机**********************************************/

    /**
     *给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int max=0;
        for (int i = 0; i < prices.length-1; i++) {
            for (int j = i+1; j < prices.length; j++) {
                if (prices[j]<=prices[i]){
                    continue;
                }
                int p = prices[j] - prices[i];
                max= Math.max(max, p);
            }
        }
        return max;
    }

    public static int maxProfit2(int[] prices) {
        int profit=0,min= prices[0];
        for (int i = 0; i < prices.length; i++) {
            if (min>prices[i]){
                min=prices[i];
            }
            int p = prices[i] - min;
            profit= Math.max(profit, p);
        }
        return profit;
    }

    /*************************************************122. 买卖股票的最佳时机 II**********************************************/

    /**
     * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
     * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
     * 返回 你能获得的 最大 利润 。
     * @param prices
     * @return
     */
    public static int maxProfitTwo(int[] prices) {
        int profit=0;
        for (int i = 1; i < prices.length; i++) {
            //贪心
//            profit+=Math.max(0,prices[i] - prices[i - 1]);
            if (prices[i]>prices[i-1]){
                int temp = prices[i] - prices[i - 1];
                profit+=temp;
            }
        }
        return profit;
    }

    public static int maxProfitTwo2(int[] prices) {
        int profit=0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i]>prices[i-1]){
                int temp = prices[i] - prices[i - 1];
                profit+=temp;
            }
        }
        return profit;
    }





    /*************************************************169. 多数元素**********************************************/
    /**
     * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     *
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * @param nums
     * @return
     */
    public static int majorityElement1(int[] nums) {
//        哈希
        if (nums.length==1){
            return nums[0];
        }
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer count = map.get(nums[i]);
            if (count!=null){
                ++count;
                if ((nums.length%2!=0 && count>= ((nums.length/2)+1)) || (nums.length%2==0 && count>= nums.length/2)){
                    return nums[i];
                }
            }else {
                count=1;
            }
            map.put(nums[i],count );
        }
        return 0;
    }

    public static int majorityElement2(int[] nums) {
        if (nums.length==1){
            return nums[0];
        }
        //排序会超时
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = 0; j < nums.length-i-1; j++) {
                if (nums[j]>=nums[j+1]){
                    int temp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=temp;
                }
            }
        }
        return nums[nums.length/2];
    }

    public static int majorityElement3(int[] nums) {
        //投票法 设置一个基准数，当前数据和基准数相同则+1，否则-1,当count==0时，将当前数据设置为基准数，众数的和将>0
        int count=0;
        Integer condition = null;

        for (int num : nums) {
            if (count==0){
                condition=num;
            }
            int vote=0;
            if (num==condition){
                vote=1;
            }else {
                vote=-1;
            }
            count=count+vote;
        }
        return condition;
    }

    public static int majorityElement4(int[] nums) {
      return majorityElementRec(nums,0,nums.length-1);
    }

    public static int majorityElementRec(int[] nums,int l,int r){
        if (l==r){
            return nums[l];
        }
       int mid=(r-l)/2+l;
        int left=majorityElementRec(nums,l,mid);
        int right=majorityElementRec(nums,mid+1,r);
        if (left==right){
            return left;
        }

        int leftCount=countInRange(nums,l,r,left);
        int rightCount=countInRange(nums,l,r,right);
        return leftCount>rightCount?left:right;

    }

    public static int countInRange(int[] nums,int l,int r,int num){
        int count=0;
        for (int i = l; i <= r; i++) {
            if (nums[i]==num){
                count++;
            }
        }
        return count;
    }

    /*************************************************189. 轮转数组**********************************************/


    /**
     *给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k) {
        //临时数组
        if (nums.length==1){
            return;
        }
        int[] temps=new int[nums.length];
        int length = nums.length;
        for (int i = 0; i < nums.length; i++) {
            int index = (i + k) > (length-1) ? ((i + k)%length) : (i + k);
            temps[index]=nums[i];
//            newArr[(i + k) % n] = nums[i];
        }
        for (int i = 0; i < temps.length; i++) {
            nums[i]=temps[i];
        }
    }

    public static void rotate2(int[] nums, int k) {
        k = k % nums.length;
        if (nums.length==1||k==0){
            return;
        }
        //翻转数组
        reverse(nums,0,nums.length-1);
        //翻转(0,k)
        reverse(nums,0,k-1);
        //翻转(k,length-1)
        reverse(nums,k,nums.length-1);


    }

    public static void reverse(int[] nums,int start,int end){
        while (start<end){
            int temp=nums[start];
            nums[start]=nums[end];
            nums[end]=temp;
            start++;
            end--;
        }
    }


    /*************************************************283. 移动零**********************************************/

    /**
     *给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     * @param nums
     */
    public static void moveZeroes(int[] nums) {
        //快慢指针
        int index=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]!=0){
                nums[index++]=nums[i];
            }
        }
        while (index<nums.length){
            nums[index++]=0;
        }
    }


    /*************************************************485. 最大连续 1 的个数**********************************************/

    /**
     * 给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
     * @param nums
     * @return
     */
    public static int findMaxConsecutiveOnes(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        int index=0,count=0;
        for (int num : nums) {
            if (num == 1) {
                ++index;
                if (count < index) {
                    count = index;
                }
            } else {
                index = 0;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {1,0,1,1,0,1};
        int ones = findMaxConsecutiveOnes(nums);
        System.out.println(ones);
    }


    /*************************************************566. 重塑矩阵**********************************************/
    /**
     * 在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
     * 给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
     * 重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
     * 如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
     * @param mat
     * @param r
     * @param c
     * @return
     */
    public static int[][] matrixReshape(int[][] mat, int r, int c) {
        int l = mat.length;
        int w = mat[0].length;
        if (l*w!=r*c){
            return mat;
        }
        //l,w [i,l*w]    f(i,j)=i*w+j   i=x/w  j=x%w
        int[][] reshapedNums = new int[r][c];
        int index=0;
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                reshapedNums[i][j]=mat[index/w][index%w];
                index++;
            }
        }
        return reshapedNums;
    }




}
